package cn.myworld.algorithm.tree;

import cn.myworld.algorithm.linear.Queue;

import java.util.TreeMap;

/**
 * 二叉查找树
 * @param <Key>
 * @param <Value>
 */

public class BinaryTree<Key extends Comparable<Key>, Value> {

    // 记录根节点
    private Node root;
    // 记录数中元素的个数
    private int N;

    private class Node {

        public Key key;

        private Value value;

        public Node left;
        public Node right;

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }

    }

    // 获取树中元素的个数
    public int size() {
        return N;
    }
    // 向树中添加元素key-value
    public void put(Key key, Value value) {
        root = put(root, key, value);
    }
    // 向指定的树x中添加key-value，并返回添加元素后新的树
    private Node put(Node x, Key key, Value value) {
        // 如果x子树为空
        if (x == null) {
            N++;
            return new Node(key, value, null, null);
        }
        // 如果x子树不为空
        // 比较x节点的键和key的大小

        if (key.compareTo(x.key) < 0) {
            // 如果key小于x节点的键，则继续找x节点的左子树
            x.left = put(x.left, key, value);
        } else if (key.compareTo(x.key) > 0) {
            // 如果key大于x节点的键，则继续找x节点的右子树
            x.right = put(x.right, key, value);
        } else {
            // 如果key等于x节点的键，则替换x节点的值value
            x.value = value;
        }

        return x;
    }
    // 查询数中指定key对应的value
    public Value get(Key key) {
        return get(root, key);
    }

    public Value get(Node x, Key key) {
        // x树为null
        if (x == null) {
            return null;
        }
        // x树不为null
        // 比较key和x节点的键的大小
        if (key.compareTo(x.key) < 0) {
            // 如果key小于x节点的键，则继续找x节点的左子树
            return get(x.left, key);
        } else if (key.compareTo(x.key) > 0) {
            // 如果key大于x节点的键，则继续找x节点的右子树
            return get(x.right, key);
        } else {
            // 如果key等于x节点的键，就找到了键为key的节点，只需要返回x节点的值
            return x.value;
        }
    }

    // 删除树中key对应的value
    public void delete(Key key) {
        delete(root, key);
    }
    // 删除指定树x中的key对应的value，并返回删除后的新树
    public Node delete(Node x, Key key) {
        // x树为null
        if (x == null) {
            return null;
        }
        // x树不为null
        if (key.compareTo(x.key) < 0) {
            // 如果key小于x节点的键，则继续找x节点的左子树
            x.left = delete(x.left, key);
        } else if (key.compareTo(x.key) > 0) {
            // 如果key大于x节点的键，则继续找x节点的右子树
            x.right = delete(x.right, key);
        } else {
            // 元素个数-1
            N--;

            // 如果key等于x节点的键，完成删除节点，要删除的节点就是x
            // 找到右子树中最小的节点
            if (x.right == null) {
                return x.left;
            } else if (x.left == null) {
                return x.right;
            }
            Node minNode = x.right;
            while (minNode.left != null) {
                minNode = minNode.left;
            }
            // 删除右子树中最小的节点
            Node n = x.right;
            while (n.left != null) {
                if (n.left.left == null) {
                    n.left = null;
                } else {
                    n = n.left;
                }
            }
            // 让x节点的左子树成为minNode的左子树
            minNode.left = x.left;
            // 让x节点的右子树成为minNode的右子树
            minNode.right = x.right;
            // 让x节点的父节点指向minNode
            x = minNode;


        }

        return x;
    }

    // 查找二叉树中最小的键
    public Key min() {
        return min(root).key;
    }
    // 在指定树x中找出最小键所在的节点
    private Node min(Node x) {
        // 判断x有没有左子节点，如果有，就继续向左找，如果没有，则x就是最小键所在的节点
        if (x.left != null) {
            return min(x.left);
        } else {
            return x;
        }
    }

    // 查找二叉树中最大的键
    public Key max() {
        return max(root).key;
    }
    // 在指定树x中找出最大键所在的节点
    private Node max(Node x) {
        // 判断x有没有右子节点，如果有，就继续向右找，如果没有，则x就是最大键所在的节点
        if (x.right != null) {
            return max(x.right);
        } else {
            return x;
        }
    }

    // TODO 不使用递归完成遍历
    // 前序遍历
    public Queue<Key> preErgodic() {
        Queue<Key> keys = new Queue<>();
        preErgodic(root, keys);
        return keys;
    }
    // 使用前序遍历，把指定树x中的所有键放入到keys队列中
    private void preErgodic(Node x, Queue<Key> keys) {
        if (x == null) {
            return;
        }
        // 1.把x节点的key放入到队列中
        keys.enqueue(x.key);
        // 2.递归遍历x节点的左子树
        if (x.left != null) {
            preErgodic(x.left, keys);
        }
        // 3.递归遍历x节点的右子树
        if (x.right != null) {
            preErgodic(x.right, keys);
        }
    }

    // 中序遍历
    public Queue<Key> midErgodic() {
        Queue<Key> keys = new Queue<>();
        midErgodic(root, keys);
        return keys;
    }
    private void midErgodic(Node x, Queue<Key> keys) {
        if (x == null) {
            return;
        }
        // 先递归，把左子树的键放到keys中
        if (x.left != null) {
            midErgodic(x.left, keys);
        }
        // 把当前节点的键放到keys中
        keys.enqueue(x.key);

        // 再递归，把右子树的键放到keys中
        if (x.right != null) {
            midErgodic(x.right, keys);
        }
    }

    // 后序遍历
    public Queue<Key> afterErgodic() {
        Queue<Key> keys = new Queue<>();
        afterErgodic(root, keys);
        return keys;
    }
    private void afterErgodic(Node x, Queue<Key> keys) {
        if (x == null) {
            return;
        }
        if (x.left != null) {
            afterErgodic(x.left, keys);
        }
        if (x.right != null) {
            afterErgodic(x.right, keys);
        }
        keys.enqueue(x.key);
    }

    // 层序遍历
    public Queue<Key> layerErgodic() {
        // 定义两个队列，分别存储树中的键和树中的节点
        Queue<Key> keys = new Queue<>();
        Queue<Node> nodes = new Queue<>();

        // 默认网队列中放入根节点
        nodes.enqueue(root);

        while (!nodes.isEmpty()) {
            // 从队列中弹出一个节点，把key放入到keys中
            Node n =  nodes.dequeue();
            keys.enqueue(n.key);
            // 判断当前节点还有没有左子节点，如果有，则放入nodes中
            if (n.left != null) {
                nodes.enqueue(n.left);
            }
            // 判断当前节点还有没有右子节点，如果有，则放入nodes中
            if (n.right != null) {
                nodes.enqueue(n.right);
            }
        }
        return keys;
    }

    // 最大深度问题
    public int maxDepth() {
        return maxDepth(root);
    }
    private int maxDepth(Node x) {
        if (x == null) {
            return 0;
        }
        int max = 0;
        int maxL = 0;
        int maxR = 0;
        // 计算x节点左子树的最大深度
        if (x.left != null) {
            maxL = maxDepth(x.left);
        }
        // 计算x节点右子树的最大深度
        if (x.right != null) {
            maxR = maxDepth(x.right);
        }

        // 比较左子树和右子树最大深度，取较大值+1
        max = maxL > maxR ? maxL + 1 : maxR + 1;

        return max;
    }

}
